|
Ore's theorem is a result in graph theory proved in 1960 by Norwegian mathematician Øystein Ore. It gives a sufficient condition for a graph to be Hamiltonian, essentially stating that a graph with "sufficiently many edges" must contain a Hamilton cycle. Specifically, the theorem considers the sum of the degrees of pairs of non-adjacent vertices: if every such pair has a sum that at least equals the total number of vertices in the graph, then the graph is Hamiltonian. ==Formal statement== Let be a (finite and simple) graph with vertices. We denote by the degree of a vertex in , i.e. the number of incident edges in to . Then, Ore's theorem states that if : for every pair of non-adjacent vertices and of ( *) then is Hamiltonian. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Ore's theorem」の詳細全文を読む スポンサード リンク
|